//
//  ProblemOffer32-1.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/5.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 32 - I. 从上到下打印二叉树
 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

 例如:
     给定二叉树: [3,9,20,null,null,15,7],

         3
        / \
       9  20
         /  \
        15   7
 返回：
    [3,9,20,15,7]
  
 提示：节点总数 <= 1000
 */
@objcMembers class ProblemOffer32_1: NSObject {
    func solution() {
        let root = TreeNode(3)
        root.left = TreeNode(9)
        root.right = TreeNode(20)
        root.right?.left = TreeNode(15)
        root.right?.right = TreeNode(7)
        print(levelOrder(root))
    }
    
    func levelOrder(_ root: TreeNode?) -> [Int] {
        if root == nil {
            return []
        }
        
        var result:[Int] = []
        var n: Int = 0
        var list: [TreeNode] = [root!]
        var node: TreeNode?
        while list.isEmpty == false {
            n = list.count
            while n > 0 {
                node = list.removeFirst()
                result.append(node!.val)
                if node?.left != nil {
                    list.append(node!.left!)
                }
                if node?.right  != nil {
                    list.append(node!.right!)
                }
                n -= 1
            }
        }
        return result
    }
}
